class Solution {
public:
    bool is_val(string &str, int i, int j) {
        if (i > j) return false;
        if (j - i > 0 && str[i] == '0') return false;
        int sum = 0;
        while (i <= j) {
            if (str[i] < '0' || str[i] > '9') return false;
            sum = sum * 10 + str[i] - '0';
            if (sum > 255) return false;
            i++;
        }
        return true;
    }
    void dfs(string &s, int index, int point, vector<string> &result) {
        if (point == 3) {
            if (is_val(s, index, s.size() - 1)) {
                result.push_back(s);
            }
            return ;
        }
        for (int i = index; i < s.size(); i++) {
            if (!is_val(s, index, i)) continue;
            s.insert(s.begin() + i + 1, '.');
            dfs(s, i + 2, point + 1, result);
            s.erase(s.begin() + i + 1);
        }
        return ;
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        dfs(s, 0, 0, result);
        return result;
    }
};
